

 


 ,
 1 








 . .
425 







         BST	2
 -     	4
      	6
     	7
	9




         BST

     BST ( )          .    ,          ,          .
      (   ):
?     ( )   .
?                    .
?-   :       ,    .
?    O(n).
?     O(n) ,              .
?     n  O(n^2).


  :
?     .
?  ,    .
?      O(logn).
?     O(logn).
?   n  O(nlogn).
:       .      O(n),      ?n/logn    ,       O(logn).





 -     


 ( )        .  ,           ,   ,      .

     :
?.    ,     .               ,        .
? .,       O(1)O(1),      ,        .
? .          ( )     ( ),         .    .
?.       .     -   ,     .
:      -,       ,      .





      

      -   :  ,         .
  :
?  .   ,      O(1),       ,     O(n).
?  .      .     :       ,           .
?   .      ,      .                 .
?   .     :
o  ,
o     ,
o   .
           .
:     O(n)   (  ),     ,       -      .




     

1.  
 :  ,         next ,   .     :   head  .
 : ,          (next),    (prev).      :prev->next = next,next->prev = prev.
:   O(n)-   ;     (     )   O(1).
2. 
  - h(key)  .       :
? :      (  ),    .
? :     ,             .
:  O(1),    O(n)(   ).
3.    (BST)
      :
?  ():  ,   .
? :           .
? :
1.(  ()    ) (  ()    ).
2. /    .
3./          .
:O(h), h  .   h=O(logn),    O(n).

 
1.  
 ꠗ      (  ),       .       O(1),    O(n)(   ,   ).
ࠗ      ,   O(1).
2.  
ࠗ       .   O(1),    O(n)(  ).
   ࠗ ,      O(logn)   .
3.      
 / ꠗ ,        ,     .    O(1),       O(n).
 ⠗    (  (O(logn)),      O(n).
    (BST)     .     O(logn).  ,             .
